package com.jxx.algorithm.datastructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


/**
 * @author LitchiShell
 * @description: 栈实例操作，给定一个表达式，计算该表达式的值
 * 思路：将表表达式转为中缀表达式--》后缀表达式（逆波兰表达式）
 * @create 2021-11-18
 */
public class MyStack {
    public static void main(String[] args) {
        String express = "1+45*(89-(56/2+1)*2+20)";
        List<String> mid = getMid(express);
        mid.forEach(System.out::println);
        List<String> last = getLast(mid);
        last.forEach(System.out::println);
        int result = calculate(last);
        System.out.println(express+"的计算结果为"+result);
    }

    /**
     * 获取中缀表达式
     * @param express
     * @return
     */
    public static List<String> getMid(String express) {
        List<String> mid = new ArrayList<>();
        int i = 0;
        do {
            // 如果自符的ASCII在不在48到57之间（数字）添加到数组
            if (express.charAt(i)<48 ||express.charAt(i) > 57) {
                mid.add(express.charAt(i)+"");
                i++;
            } else {
                String value = ""; //组装数值
                while(express.charAt(i) >= 48 && express.charAt(i) <= 57 && i <express.length()) {
                    value += express.charAt(i);//数值拼接
                    i++;
                }
                mid.add(value);
            }
        } while(i < express.length());
        return mid;
    }

    /**
     * 中缀---》后缀
     * @param mid
     * @return
     */
    public static List<String> getLast(List<String> mid) {
        Stack<String> stack = new Stack<>();
        List<String> last = new ArrayList<>();
        for (String m : mid) {
            // 数字直接进入列表
            if (m.matches("\\d+")) {
                last.add(m);
            } else if("(".equals(m)) { // "("进入栈
                stack.push(m);
            } else if(")".equals(m)) { // ")"将栈中的元素弹出栈中并加入列表，知道遇到")"
                while(!"(".equals(stack.peek())) {
                    last.add(stack.pop());
                }
                stack.pop();// "(" 弹出栈
            } else { //比较传入列表的元素和栈顶元素的权值,如果栈顶元素权值大的先添加到列表，否则列表元素如栈
                while(stack.size() != 0 && Operator.getValue(stack.peek()) >= Operator.getValue(m)) {
                    last.add(stack.pop());
                }
                stack.push(m);
            }
        }
        // 将栈中的元素添加到列表中
        while(stack.size() != 0) {
            last.add(stack.pop());
        }
        return last;
    }

    /**
     * 计算表达式
     * @param last
     * @return
     */
    public static int calculate(List<String> last) {
        Stack<String> stack = new Stack<>();
        for (String l : last) {
            if (l.matches("\\d+")) { //数字入栈
                stack.push(l);
            } else { // 不是数字，从栈中弹出两个数
                Integer result = 0;
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                if ("*".equals(l)) {
                    result = num1 * num2;
                } else if("+".equals(l)) {
                    result = num1 + num2;
                } else if("-".equals(l)) {
                    result = num2 - num1;//注意：先出栈的作为减数或除数
                } else if("/".equals(l)){
                    result = num2 / num1;
                } else {
                    System.out.println("运算错误");
                }
                // 将计算结果入栈
                stack.push(result+"");
            }
        }
        // 最后弹出的结果即为计算结果
        return Integer.valueOf(stack.pop());
    }
}


/**
 * 定义一个表示操作符优先级的类
 */
class Operator {
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;

    /**
     * 根据传递的运算符获取对应的权值
     * @param Operator
     * @return
     */
    public static int getValue(String Operator) {
        int value = 0;
        switch (Operator) {
            case "+":
                value =  ADD;
                break;
            case "-":
                value = SUB;
                break;
            case "*":
                value = MUL;
                break;
            case "/":
                value = DIV;
                break;
            default:
                System.out.println("该符号不是基本运算符");
                break;
        }
        return value;
    }
}